package com.sheng.leetcode.year2023.month04.day06;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/04/06
 * <p>
 * 1017. 负二进制转换<p>
 * <p>
 * 给你一个整数 n ，以二进制字符串的形式返回该整数的 负二进制（base -2）表示。<p>
 * 注意，除非字符串就是 "0"，否则返回的字符串中不能含有前导零。<p>
 * <p>
 * 示例 1：<p>
 * 输入：n = 2<p>
 * 输出："110"<p>
 * 解释：(-2)^2 + (-2)^1 = 2<p>
 * <p>
 * 示例 2：<p>
 * 输入：n = 3<p>
 * 输出："111"<p>
 * 解释：(-2)^2 + (-2)^1 + (-2)^0 = 3<p>
 * <p>
 * 示例 3：<p>
 * 输入：n = 4<p>
 * 输出："100"<p>
 * 解释：(-2)^2 = 4<p>
 * <p>
 * 提示：<p>
 * 0 <= n <= 10^9<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/convert-to-base-2">1017. 负二进制转换</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1017 {

    @Test
    public void test01() {
//        int n = 2;
//        int n = 3;
        int n = 4;
        System.out.println(new Solution().baseNeg2(n));
    }
}

class Solution {
    public String baseNeg2(int n) {
        if (n == 0) {
            return "0";
        }
        int k = 1;
        StringBuilder ans = new StringBuilder();
        while (n != 0) {
            if (n % 2 != 0) {
                ans.append(1);
                n -= k;
            } else {
                ans.append(0);
            }
            k *= -1;
            n /= 2;
        }
        return ans.reverse().toString();
    }
}
